{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Plus Court Chemin dans un Graphe Pondéré\n",
    "\n",
    "Dans cette partie, on essaye de trouver le chemin le plus court pour aller d'un point à un autre sur une carte.\n",
    "Pour cela, on peut utiliser des parcours de graphes.\n",
    "\n",
    "**Question 0.** Quel type de parcours de graphes utiliser pour trouver le plus court chemin entre deux points ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Réponse :*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Terrain de jeu."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from matplotlib.collections import LineCollection\n",
    "from matplotlib.colors import ListedColormap\n",
    "cmap = ListedColormap([\"sandybrown\", \"aquamarine\"])\n",
    "\n",
    "def afficher_terrain(terrain, chemin=None):\n",
    "    plt.imshow(terrain, cmap=cmap)\n",
    "    plt.axis(\"off\");\n",
    "    \n",
    "    if chemin is not None:\n",
    "        solx = [v for (u, v) in chemin]\n",
    "        soly = [u for (u, v) in chemin]\n",
    "        plt.plot(solx, soly, color=\"red\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction ci-dessus permet d'afficher un terrain de jeu, représenté sous la forme d'une matrice.\n",
    "Prenons le terrain suivant, où la terre est représentée en marron et l'eau en bleu."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "terrain = np.zeros((10, 10))\n",
    "terrain = np.array(\n",
    "      [[0, 0, 1, 1, 0, 0, 0, 0, 0, 0],\n",
    "       [0, 0, 1, 0, 0, 0, 1, 0, 0, 0],\n",
    "       [0, 1, 1, 0, 0, 1, 1, 1, 0, 0],\n",
    "       [0, 1, 1, 0, 1, 1, 1, 1, 1, 0],\n",
    "       [0, 0, 1, 0, 0, 1, 1, 0, 0, 0],\n",
    "       [0, 0, 0, 0, 0, 0, 1, 0, 0, 0],\n",
    "       [0, 0, 0, 0, 0, 1, 1, 0, 0, 0],\n",
    "       [0, 0, 0, 0, 1, 1, 0, 0, 0, 0],\n",
    "       [0, 0, 0, 1, 1, 1, 0, 0, 0, 0],\n",
    "       [0, 0, 0, 0, 0, 1, 1, 0, 0, 0]])\n",
    "\n",
    "afficher_terrain(terrain)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Coûts des Déplacements."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Représentons ce terrain sous la forme d'un graphe pondéré.\n",
    "Les sommets du graphe seront les cases du terrain, la case de coordonnées $(x, y)$ ayant pour nom $(x, y)$.\n",
    "\n",
    "Supposons que l'on puisse facilement se déplacer d'une case de terre à un autre, et que l'on se déplace avec un peu plus de difficulté dans l'eau.\n",
    "En revanche, on n'a vraiment pas envie de se mouiller, donc passer d'une case de terre à une case d'eau nous demande beaucoup de préparations et d'énergie.\n",
    "\n",
    "Résumons cela par les règles de déplacements suivantes :\n",
    "* passer d'une case de terre à une case de terre a un coût de $1$ ;\n",
    "* passer d'une case d'eau à une case d'eau a un coût de $2$ ;\n",
    "* passer d'une case de terre à une d'eau ou le contraire a un coût de $200$.\n",
    "\n",
    "On peut alors traduire notre carte par un graphe pondéré, dont les poids sont ceux décrits au dessus."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les fonctions suivantes sont des fonctions qui génèrent le graphe correspondant au terrain et des fonctions d'affichage."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def valeur(u, v, val_eau=200):\n",
    "    if u + v == 0:\n",
    "        return 1\n",
    "    if u + v == 1:\n",
    "        return val_eau\n",
    "    else:\n",
    "        return 2\n",
    "    \n",
    "valeur_normale = lambda u, v: valeur(u, v, 200)\n",
    "valeur_nulle = lambda u, v: valeur(u, v, 0)\n",
    "\n",
    "def graphe_terrain(terrain, valeur=valeur_normale):\n",
    "    width, height = terrain.shape\n",
    "    \n",
    "    aretes_poids =  [((u, v), (u+1,v), valeur(terrain[u,v], terrain[u+1,v])) \\\n",
    "                      for u in range(width - 1) for v in range(height)]\n",
    "    aretes_poids += [((u, v), (u,v+1), valeur(terrain[u,v], terrain[u,v+1])) \\\n",
    "                      for u in range(width) for v in range(height-1)]\n",
    "    \n",
    "    G = nx.Graph()\n",
    "    G.add_weighted_edges_from(aretes_poids)\n",
    "    \n",
    "    return G\n",
    "\n",
    "\n",
    "def afficher_graphe_terrain(Gterrain, terrain):\n",
    "    fig, ax = plt.subplots(figsize=(10,10))\n",
    "\n",
    "    pos = {(u, v): (v, terrain.shape[0]-u) for u in range(terrain.shape[0]) for v in range(terrain.shape[1])}\n",
    "    aretes_poids = {(u,v,): d['weight'] for u,v,d in Gterrain.edges(data=True)}\n",
    "\n",
    "    nx.draw(Gterrain, pos,\n",
    "        node_color=[\"sandybrown\" if terrain[u] == 0 else \"aquamarine\" for u in Gterrain.nodes()],\n",
    "        edgecolors=\"black\")\n",
    "    nx.draw_networkx_edge_labels(Gterrain,pos,edge_labels=aretes_poids);\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Graphe des déplacements.\n",
    "\n",
    "Affichons le graphe correspondant au terrain ci-dessus.\n",
    "Les sommets du graphe ont pour étiquette les coordonées $(x, y)$ de la case du terrain à laquelle ils correspondent, et les arêtes sont pondérées par le coût du passage d'un sommet à un autre."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Gterrain = graphe_terrain(terrain)\n",
    "\n",
    "afficher_graphe_terrain(Gterrain, terrain)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voilà une fonction qui prend un graphe en entrée et qui renvoit sa liste d'adjacence."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def liste_adjacence(G):\n",
    "    adj = {}\n",
    "    \n",
    "    for sommet, adjacence in G.adjacency():\n",
    "        adj[sommet] = adjacence.keys()\n",
    "        \n",
    "    return adj"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Recherche de Chemin.\n",
    "\n",
    "Pour trouver le chemin le plus court dans ce graphe pondéré, on procède comme pour trouver le chemin le plus court dans un graphe non pondéré.\n",
    "\n",
    "On part donc d'un sommet, puis on visite ses voisins, et ainsi de suite.\n",
    "Seulement, quand on rencontre un nouveau voisin, on a deux possibilités :\n",
    "* soit on ne l'a jamais rencontré, et le chemin actuel est le plus court pour l'instant ;\n",
    "* soit on l'a déjà rencontré, auquel cas, soit le chemin actuel est plus court, et peut donc remplacer le chemin déjà connu, soit il est plus long, et on peut l'ignorer.\n",
    "\n",
    "On ne gardera donc plus en mémoire l'ensemble des sommets que l'on a déjà visités, mais la longueur du chemin le plus court que l'on connaît jusqu'à ce sommet."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question 1.** Implémentez une fonction `plus_court_chemin` qui prend en entrée un graphe pondéré et qui renvoit le plus court chemin (sous la forme d'une liste de sommets) entre les deux sommets s'il en existe un, et qui renvoie `False` sinon.\n",
    "\n",
    "On pourra garder en mémoire :\n",
    "* une queue`a_visiter` (utiliser par exemple `deque`) des sommets qui restent à visiter ;\n",
    "* un dictionnaire `predecesseur` qui associe à chaque sommet son prédécesseur dans le chemin le plus court connu jusqu'ici ;\n",
    "* un dictionnaire `distance` qui associe à chaque sommet sa distance au sommet de départ. Au début, ce dictionnaire associera la valeur `np.inf` à tous les sommets sauf au sommet de départ, auquel il associera `0`. De cette façon, on pourra facilement calculer si le chemin courant est plus court ou plus long qu'un chemin déjà connu.\n",
    "\n",
    "Remarques :\n",
    "* on peut récupérer le poids d'une arête $(u, v)$ en utilisant : `poids = G.get_edge_data(u, v)[\"weight\"]` ;\n",
    "* la fonction `liste_adjacence` ci-dessus renvoie la liste d'adjacence du graphe sous forme d'un dictionnaire dont les valeurs sont les listes d'adjacences et les clés les sommets (comme en TP)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "\n",
    "def plus_court_chemin(G, s1, s2):\n",
    "    # ~~~ implémeter la fonction ~~~"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question 2.** Utilisez votre fonction pour afficher le plus court chemin partant d'en haut à gauche (sommet $(0, 0)$) jusqu'au sommet en bas à droite (sommet $(9, 9)$).\n",
    "\n",
    "Vous pourrez utiliser la fonction `afficher_terrain` en lui donnant `terrain` comme premier argument et votre chemin se second argument."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "afficher_terrain(terrain, chemin)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Supposons maintenant que l'on ait extrêmement envie de plonger, et donc que, maintenant, passer de la terre ferme à l'eau a un coût de $0$.\n",
    "\n",
    "Le graphe correspondant aux coûts de déplacements sur notre terrain est donc maintenant le suivant :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "Gterrain0 = graphe_terrain(terrain, valeur_nulle)\n",
    "afficher_graphe_terrain(Gterrain0, terrain)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question 3.** Avec ces nouvelles règles de déplacement, affichez le plus court chemin entre les sommets $(0, 0)$ et $(9, 9)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "afficher_terrain(terrain, chemin0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question 4.** Commentez le chemin obtenu. Est-ce bien le chemin le plus court ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Réponse :*"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}